package io.github.handyang.algorithms.digraph;

/**
 * 有向图的可达性
 */
public class DirectedDFS {

    private final Digraph digraph;

    private final boolean[] marked;

    /**
     * 单点可达性
     *
     * @param digraph
     * @param start
     */
    public DirectedDFS(Digraph digraph, int start) {
        this.digraph = digraph;
        this.marked = new boolean[digraph.V()];

        dfs(start);
    }

    /**
     * 多点可达性
     *
     * @param digraph
     * @param startSource
     */
    public DirectedDFS(Digraph digraph, Iterable<Integer> startSource) {
        this.digraph = digraph;
        this.marked = new boolean[digraph.V()];

        for (Integer s : startSource) {
            if (marked[s]) continue;

            dfs(s);
        }
    }

    private void dfs(int start) {
        marked[start] = true;

        for (Integer point : digraph.adj(start)) {
            if (marked[point]) continue;

            dfs(point);
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }
}


